#pragma once

class CSweepCircleVoronoi
{
public:
	struct Vertex;
	struct Edge;
	struct Point;
	static vector<Vertex> vertexPool;
	static vector<Edge> edgePool;
	static vector<Point> sites;
	static Point center;
	static Point minPoint;
	static Point maxPoint;
public:
	struct Point
	{
		float x;
		float y;
		Point(){}
		Point(float x, float y) : x(x), y(y){}
		bool operator==(const Point& other) const
		{
			return x == other.x && y == other.y;
		}
	};
	struct Vertex
	{
		float x;
		float y;
		Vertex(){}
		Vertex(float x, float y) : x(x), y(y){}
		Vertex(Point pt): x(pt.x), y(pt.y){}
	};
	struct Edge
	{
		int vert1;
		int vert2;
		Edge(){}
		Edge(int vert1, int vert2) : vert1(vert1), vert2(vert2){}
	};
	struct Ellipse;
	struct EllipseArc;
	struct ActiveEdge
	{
		EllipseArc* leftArc;
		EllipseArc* rightArc;
		int fixedVertex;
		Point direction;
		ActiveEdge(EllipseArc* leftArc, EllipseArc* rightArc, int fixedVertex): leftArc(leftArc), rightArc(rightArc), fixedVertex(fixedVertex)
		{
			Point p1 = leftArc->minorFocus;
			Point p2 = rightArc->minorFocus;
			direction = GetDirection(p1, p2);
		}
		
		Point GetCurrentPos(float d)
		{
			if (leftArc == NULL || rightArc == NULL)
			{
			assert(leftArc != NULL && rightArc != NULL);
			}
			if (leftArc->GetP(d) < FLT_EPSILON && rightArc->GetP(d) < FLT_EPSILON)
			{
				return leftArc->majorFocus;
			}
			if (leftArc->GetP(d) < FLT_EPSILON)
			{
				float angle = atan2(leftArc->minorFocus.y - leftArc->majorFocus.y, leftArc->minorFocus.x - leftArc->majorFocus.x);
				return rightArc->GetPointAtAngleParam(d, angle);
			}
			if (rightArc->GetP(d) < FLT_EPSILON)
			{
				float angle = atan2(rightArc->minorFocus.y - rightArc->majorFocus.y, rightArc->minorFocus.x - rightArc->majorFocus.x);
				return leftArc->GetPointAtAngleParam(d, angle);
			}

			Point params = Ellipse::GetIntersectionAngleParam(*leftArc, *rightArc, d);
			Point p1 = leftArc->GetPointAtAngleParam(d, params.x);
			Point p2 = leftArc->GetPointAtAngleParam(d, params.y);
			if ((p2.x - p1.x) * direction.x + (p2.y - p1.y) * direction.y > 0)
			{
				return p2;
			}
			return p1;
		}
		static Point GetDirection(Point p1, Point p2)
		{
			float x = p1.y - p2.y;
			float y = p2.x - p1.x;
			float len = sqrt(x * x + y * y);
			return Point(x / len, y / len);
		}
	};
	struct Ellipse
	{
		Point majorFocus;
		Point minorFocus;
		float rotateAngle;
		float c;
		Ellipse(Point majorFocus, Point minorFocus) : majorFocus(majorFocus), minorFocus(minorFocus) 
		{
			float detaX = minorFocus.x - majorFocus.x;
			float detaY = minorFocus.y - majorFocus.y;
			rotateAngle = atan2(detaY, detaX);
			c = sqrt((majorFocus.x - minorFocus.x) * (majorFocus.x - minorFocus.x) + (majorFocus.y - minorFocus.y) * (majorFocus.y - minorFocus.y)) / 2;
		}
		float GetA(float d) const
		{
			return d / 2;
		}
		float GetC() const
		{			
			return c;
		}
		float GetE(float d) const
		{
			return GetC() / GetA(d);
		}
		float GetP(float d) const
		{
			float a = GetA(d);
			float c = GetC();
			return a * a / c - c;
		}
		float GetRotateAngle() const
		{
			return rotateAngle;
		}
		Point GetPointAtAngleParam(float d, float angle) const
		{
			float e = GetE(d);
			float p = GetP(d);
			if (!(p > FLT_EPSILON))
			{
				assert (p > FLT_EPSILON);
			}
			float alpha = GetRotateAngle();
			float rou = e * p / (1 - e * cos(angle - alpha));
			Point pt(rou * cos(angle), rou * sin(angle));
			pt.x += majorFocus.x;
			pt.y += majorFocus.y;
			return pt;
		}
		static Point GetIntersectionAngleParam(const Ellipse& ellipse1, const Ellipse& ellipse2, float d)
		{
			float e1 = ellipse1.GetE(d);
			float e2 = ellipse2.GetE(d);
			float p1 = ellipse1.GetP(d);
			float p2 = ellipse2.GetP(d);
			float alpha1 = ellipse1.GetRotateAngle();
			float alpha2 = ellipse2.GetRotateAngle();
			float a = p2 * cos(alpha1) - p1 * cos(alpha2);
			float b = p2 * sin(alpha1) - p1 * sin(alpha2);
			float c = (e2 * p2 - e1 * p1) / (e1 * e2);
			float len = sqrt(a * a + b * b);
			a /= len;
			b /= len;
			c /= len;
			float t = atan2(b, a);
			float t2;
			if (c >= 1)
				t2 = 0;
			else if (c <= -1)
				t2 = M_PI;
			else
				t2 = acos(c);
			return Point(t - t2, t + t2);
		}
	};
	struct Event;
	struct EllipseArc : Ellipse
	{
		bool outofdate;
		ActiveEdge* leftActiveEdge;
		ActiveEdge* rightActiveEdge;
		static const float tolerance;
		EllipseArc(Point majorFocus, Point minorFocus, ActiveEdge* leftActiveEdge, ActiveEdge* rightActiveEdge) : Ellipse(majorFocus, minorFocus), leftActiveEdge(leftActiveEdge), rightActiveEdge(rightActiveEdge)
		{
			outofdate = false;
		}
		pair<float, Event> GetVanishEvent()
		{
			Event evt;
			evt.type = EllipseVanish;
			float keyDis = FLT_MAX;			
			evt.arc = this;
			if (leftActiveEdge == NULL || rightActiveEdge == NULL)
				return pair<float, Event>(keyDis, evt);
			if (leftActiveEdge->fixedVertex == rightActiveEdge->fixedVertex)
				return pair<float, Event>(keyDis, evt);
			if (abs(leftActiveEdge->direction.x * rightActiveEdge->direction.x + leftActiveEdge->direction.y * rightActiveEdge->direction.y) > 1.0 - FLT_EPSILON)
				return pair<float, Event>(keyDis, evt);
			
			float e1 = vertexPool[leftActiveEdge->fixedVertex].x - vertexPool[rightActiveEdge->fixedVertex].x;
			float e2 = vertexPool[leftActiveEdge->fixedVertex].y - vertexPool[rightActiveEdge->fixedVertex].y;

			float a = -leftActiveEdge->direction.x;
			float b = rightActiveEdge->direction.x;
			float c = -leftActiveEdge->direction.y;
			float d = rightActiveEdge->direction.y;
			float mod = a * d - b * c;
			float tLeft = d * e1 - b * e2;
			tLeft /= mod;
			float tRight = -c * e1 + a * e2;
			tRight /= mod;

			if (tLeft < -FLT_EPSILON || tRight < -FLT_EPSILON)
			{
				return pair<float, Event>(keyDis, evt);
			}
			if (tLeft < 0)
				tLeft = 0;
			if (tRight < 0)
				tRight = 0;
			
			Point circumcenter;
			circumcenter.x = vertexPool[leftActiveEdge->fixedVertex].x + tLeft * leftActiveEdge->direction.x;
			circumcenter.y = vertexPool[leftActiveEdge->fixedVertex].y + tLeft * leftActiveEdge->direction.y;

			float dis = sqrt((circumcenter.x - minorFocus.x) * (circumcenter.x - minorFocus.x) + (circumcenter.y - minorFocus.y) * (circumcenter.y - minorFocus.y));
			dis += sqrt((circumcenter.x - majorFocus.x) * (circumcenter.x - majorFocus.x) + (circumcenter.y - majorFocus.y) * (circumcenter.y - majorFocus.y));
			keyDis = dis;
			evt.leftActiveEdge = leftActiveEdge;
			evt.rightActiveEdge = rightActiveEdge;
			evt.site = circumcenter;
			return pair<float, Event>(keyDis - tolerance, evt);
		}

		bool Zero(float d)
		{
			Point angles = GetAngles(d);
			return angles.y - angles.x < FLT_EPSILON;
		}

		Point GetAngles(float d)
		{
			if (leftActiveEdge == NULL)
			{
				return Point(0, 2 * M_PI);
			}
			assert (rightActiveEdge != NULL);
			
			if (GetP(d) < FLT_EPSILON)
			{
				assert(!(abs(minorFocus.y - majorFocus.y) + abs(minorFocus.x - majorFocus.x) < FLT_EPSILON));				
				return Point(GetRotateAngle(), GetRotateAngle());
			}
			Point leftP = leftActiveEdge->GetCurrentPos(d);
			Point rightP = rightActiveEdge->GetCurrentPos(d);

			assert(!(abs(rightP.y - majorFocus.y) + abs(rightP.x - majorFocus.x) < FLT_EPSILON));
			float angle1 = atan2(rightP.y - majorFocus.y, rightP.x - majorFocus.x);
			assert(!(abs(leftP.y - majorFocus.y) + abs(leftP.x - majorFocus.x) < FLT_EPSILON));
			float angle2 = atan2(leftP.y - majorFocus.y, leftP.x - majorFocus.x);

			if (angle2 < angle1 - FLT_EPSILON)
			{
				angle2 += 2 * M_PI;
			}
			else if (angle2 < angle1 + FLT_EPSILON && leftActiveEdge->leftArc == rightActiveEdge->rightArc)
			{
				angle2 += 2 * M_PI;
			} 
			else if (angle2 - angle1 > 2 * M_PI - FLT_EPSILON)
			{
				angle1 = angle2;
			}
			return Point(angle1, angle2);
		}
		vector<vector<Point> > GetSegments(float d)
		{
			float minAngle = -M_PI;
			float maxAngle = M_PI;
			int xRegionCode = 0;
			int yRegionCode = 0;
			if (center.x > maxPoint.x)
			{
				xRegionCode = 1;
			}
			else if (center.x < minPoint.x)
			{
				xRegionCode = -1;
			}
			if (center.y > maxPoint.y)
			{
				yRegionCode = 1;
			}
			else if (center.y < minPoint.y)
			{
				yRegionCode = -1;
			}

			if (xRegionCode == 0 && yRegionCode == 0)
			{
				minAngle = -M_PI;
				maxAngle = M_PI;
			}
			else if (xRegionCode == 1 && yRegionCode == 0)
			{
				minAngle = atan2(maxPoint.y - CSweepCircleVoronoi::center.y, maxPoint.x - CSweepCircleVoronoi::center.x);
				maxAngle = atan2(minPoint.y - CSweepCircleVoronoi::center.y, maxPoint.x - CSweepCircleVoronoi::center.x) + 2 * M_PI;
			}
			else
			{
				float angles[4] = {atan2(maxPoint.y - CSweepCircleVoronoi::center.y, maxPoint.x - CSweepCircleVoronoi::center.x),
				atan2(maxPoint.y - CSweepCircleVoronoi::center.y, minPoint.x - CSweepCircleVoronoi::center.x),
				atan2(minPoint.y - CSweepCircleVoronoi::center.y, minPoint.x - CSweepCircleVoronoi::center.x),
				atan2(minPoint.y - CSweepCircleVoronoi::center.y, maxPoint.x - CSweepCircleVoronoi::center.x)};
				minAngle = 10;
				maxAngle = -10;
				for (int i = 0; i < 4; ++i)
				{
					if (angles[i] > maxAngle)
						maxAngle = angles[i];
					if (angles[i] < minAngle)
						minAngle = angles[i];
				}
			}

			vector<vector<Point> > resPoints;
			if (GetP(d) < FLT_EPSILON)
			{
				resPoints.push_back(vector<Point>());
				resPoints[0].push_back(minorFocus);
				if (leftActiveEdge == NULL)
				{
					resPoints[0].push_back(majorFocus);
				}
				else if (leftActiveEdge->leftArc->GetP(d) > FLT_EPSILON)
				{
					resPoints[0].push_back(leftActiveEdge->leftArc->GetPointAtAngleParam(d, this->GetRotateAngle()));		
				}
				else if (rightActiveEdge->rightArc->GetP(d) > FLT_EPSILON)
				{
					resPoints[0].push_back(rightActiveEdge->rightArc->GetPointAtAngleParam(d, this->GetRotateAngle()));		
				}
				else
				{
					resPoints[0].push_back(majorFocus);
				}
				return resPoints;
			}
			Point angles = GetAngles(d);
			Point angles2(1, -1);
			if (angles.x < -10 || angles.y > 10)
			{
				assert(false);
			}
			if (maxAngle <= M_PI && angles.y <= M_PI)
			{
				angles.y = min(angles.y, maxAngle);
				angles.x = max(angles.x, minAngle);
			}
			else if (maxAngle > M_PI && angles.y <= M_PI)
			{
				angles2 = Point(angles.x, maxAngle - M_PI);
				angles.x = minAngle;
			}
			else if (maxAngle <= M_PI && angles.y > M_PI)
			{
				angles2 = Point(angles.x, maxAngle);
				angles.x = minAngle;
				angles.y -= 2 * M_PI;
			}
			else
			{
				angles.x = max(angles.x, minAngle);
				angles.y = min(angles.y, maxAngle);
			}

			float deta = (maxAngle - minAngle) / 360;
			if (angles.x < angles.y)
			{
				resPoints.push_back(vector<Point>());
				int pos = resPoints.size() - 1;
				for (float angle = angles.x; angle <= angles.y; angle += deta)
				{
					resPoints[pos].push_back(GetPointAtAngleParam(d, angle));
				}
				resPoints[pos].push_back(GetPointAtAngleParam(d, angles.y));
			}


			if (angles2.x < angles2.y)
			{
				resPoints.push_back(vector<Point>());
				int pos = resPoints.size() - 1;
				for (float angle = angles2.x; angle <= angles2.y; angle += deta)
				{
					resPoints[pos].push_back(GetPointAtAngleParam(d, angle));
				}
				resPoints[pos].push_back(GetPointAtAngleParam(d, angles2.y));
			}
			return resPoints;
		}
	};

	enum EventType {NewEllipse, EllipseVanish};
	struct Event
	{
		int type; 
		//double d;
		Point site;
		EllipseArc* arc;
		ActiveEdge* leftActiveEdge;
		ActiveEdge* rightActiveEdge;
	};

public:
	CSweepCircleVoronoi(const vector<Point>& inputsites, Point center);
	~CSweepCircleVoronoi(void);
	
	bool BuildVoronoiDiagram();
	bool BuildVoronoiDiagram(float d);
	void Initialize();
	pair<float, Event> GetNextEvent();

private:
void processInactiveArcs( EllipseArc* leftArc ,EllipseArc* headArc, bool flagHeadArcReplace );
	void HandleOneLevel();
	void RemoveOutofdateEvents();
	void Clean();
	priority_queue<priority_structure<float, Event>> eventQue;
	vector<EllipseArc*> toBeDeletedArcs;
	vector<ActiveEdge*> toBeDeletedEdges;

public:
	float distance;
	float distanceGap;
	EllipseArc *headArc;
};
